package DP.Lesson7;

import java.util.*;

/**
 * https://www.lintcode.com/problem/k-sum/description
 */
public class KSum {

    /**
     * 背包问题
     * 简单的背包问题 dp[i] = dp[j] + A[i] 这是一维的
     * dp[i][k][s] = 选中i数字的，第k个数字，和等于s  有多少种
     */
    public int kSum(int[] A, int k, int target) {
        int n = A.length;
        if(n == 0) return 0;
        int[][][] dp = new int[n+1][k+1][target+1];

        dp[0][0][0] = 1;
        for(int i=1; i<=n; i++){//因为必须要选中1个数，i是选中几个数
            for(int j=0;j<=k; j++){//这里从0开始是因为，要看0个数的情况
                for(int p=0; p <= target; p++){
                    dp[i][j][p] = dp[i-1][j][p];//这一句是因为求总的组合，那么i的 就需要继承自 i-1的，再求出来 使用i的
                    if(j>0 && p >= A[i-1]){
                        //当目标值大于A[i-1]的时候，就需要加上 上一个数的dp总和
                        dp[i][j][p] += dp[i-1][j-1][p-A[i-1]];
                    }
                }
            }
        }

        return dp[n][k][target];
    }


    /**
     * https://leetcode-cn.com/problems/3sum/
     * 这个要求打印出组合
     * 这个就用不到DP了，先排序，然后，双指针，先一个指针是k，从1--n-2 遍历，然后，内部循环左右指针找i和j
     * 细节的处理要注意，有重复值就跳过
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int i,j,sum;
        for(int k=0; k<nums.length-2;k++){
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            i=k+1; j=nums.length-1;
            while ( i < j){
                sum = nums[i] + nums[j] + nums[k];
                //小于的话，左边加，大于的话右边移动
                if(sum < 0){
                    while (i<j && nums[i]==nums[++i]);
                }
                else if(sum >0){
                    while (i<j && nums[j]==nums[--j]);
                }
                else{
                    List<Integer> r = new ArrayList<>();
                    r.add(nums[i]);r.add(nums[j]);r.add(nums[k]);
                    res.add(r);
                    while (i<j && nums[i]==nums[++i]);
                    while (i<j && nums[j]==nums[--j]);
                }
            }
        }
        return res;
    }

//    Arrays.sort(nums);
//    List<List<Integer>> res = new ArrayList<>();
//        for(int k = 0; k < nums.length - 2; k++){
//        if(nums[k] > 0) break;
//        if(k > 0 && nums[k] == nums[k - 1]) continue;
//        int i = k + 1, j = nums.length - 1;
//        while(i < j){
//            int sum = nums[k] + nums[i] + nums[j];
//            if(sum < 0){
//                while(i < j && nums[i] == nums[++i]);
//            } else if (sum > 0) {
//                while(i < j && nums[j] == nums[--j]);
//            } else {
//                res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
//                while(i < j && nums[i] == nums[++i]);
//                while(i < j && nums[j] == nums[--j]);
//            }
//        }
//    }


    /**
     * https://leetcode-cn.com/problems/two-sum/
     * 当年挂的那题
     * 1.hash存储；
     * 2.
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> m = new HashMap<>();
        int n=nums.length;
        int[] res = new int[2];
        for(int i=0; i< n; i++){
            //妹的，没想到这么简单的题目，还有小细节，要注意存的是 另外一个
            //表示有重复数字，需要特别处理下，如果相等直接返回
            if(m.containsKey(nums[i])){
                res[0] = m.get(nums[i]);
                res[1] = i;
                return res;
            }
            m.put(target - nums[i], i);
        }

        return res;
    }

    public static void main(String[] args){
        KSum k = new KSum();
        int[] a={-1,0,1,2,-1,-4};
        System.out.println( k.threeSum(a) );

    }


}
